package com.xj.algorithm.leetcode;

/**
 * 汉明距离
 *
 * 广泛应用于信息论中的错误检测
 */
public class L461_汉明距离 {

    /**
     * 两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
     *
     * 给出两个整数 x 和 y，计算它们之间的汉明距离。
     *
     * 注意：
     * 0 ≤ x, y < 231.
     *
     * 示例:
     *
     * 输入: x = 1, y = 4
     *
     * 输出: 2
     *
     * 解释:
     * 1   (0 0 0 1)
     * 4   (0 1 0 0)
     *        ↑   ↑
     *
     * 上面的箭头指出了对应二进制位不同的位置。
     */
    public static void main(String[] args) {
        System.out.println(hammingDistance(1,4));
        System.out.println(hammingDistance(93,73));

        System.out.println(hammingDistanceOffice(93,73));
    }

    //自己的解法：先异或，然后统计1个数有多少个1
    public static int hammingDistance(int x, int y) {
        int n=x^y;  //异或操作

        int sum = 0;
        while (n != 0) {
            sum++;
            n &= (n - 1);   //与操作
        }
        return sum;
    }

    //官方解法：内置为计数器功能
    public static int hammingDistanceOffice(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}
